package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/4/27 19:17
 * @description ：前序和后序结果 构建树结构
 * @modifiedBy ：
 */
public class BinaryTreeByPreorderAndInorderConstructor {


    /**
     * 根据先序遍历和后序遍历结果来构建二叉树
     * @param preorderResult
     * @param inorderResult
     * @return
     */
    public TreeNode construct(int[] preorderResult, int[] inorderResult){



        return construct(preorderResult, inorderResult, 0, preorderResult.length-1, 0, inorderResult.length-1);
    }

    public TreeNode construct(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {

        if (preLeft > preRight) {
            return null;
        }

        TreeNode now = new TreeNode(preorder[preLeft]);
        // 通过中间节点 将 postorderResult分成两部分
        int inMiddle = inLeft;
        int tempIn = inLeft;
        while(tempIn <= inRight) {
            if (now.val == inorder[tempIn]) {
                inMiddle = tempIn;
                break;
            }
            tempIn++;
        }
        int leftTreeLength = inMiddle-inLeft;
        int rightTreeLength = inRight-inMiddle;
        // 构建左子树
        now.left = construct(preorder, inorder, preLeft+1, preLeft+leftTreeLength, inLeft, inMiddle-1);
        now.right = construct(preorder, inorder, preLeft+leftTreeLength+1, preRight, inMiddle+1, inRight);

        return now;
    }

    public static void main(String[] args) {
        BinaryTreeByPreorderAndInorderConstructor constructor = new BinaryTreeByPreorderAndInorderConstructor();
        TreeNode root = constructor.construct(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7});

    }
}
